/*
 * @Author       : wangzeyu 2309335887@qq.com
 * @Date         : 2023-07-16 15:08:49
 * @LastEditors  : WangZeYu
 * @LastEditTime : 2023-07-16 17:43:32
 * @FilePath     : \algorithm\knapsack.js
 * @Description  : 01背包问题(动态规划)
 */

// [                 容量j=0  容量j=1 容量j=2 容量j=3 容量j=4  容量j=5
//物品i=0(容量2，值3)   [ 0,    0,      3,      3,      3,      3 ], 
//物品i=1(容量3，值4)   [ 0,    0,      3,      4,      4,      7 ], 
//物品i=2(容量4，值5)   [ 0,    0,      3,      4,      5(i=2,j=4),      7(i=2,j=5) ]
// ]                                                    (i=1,j=0)        (i=1,j=1)

function knapsack(weights, values, capacity) {
  let T = []
  let n = weights.length

  for (let i = 0; i < n; i++) {
    T[i] = [];
    for (let j = 0; j <= capacity; j++) {
      // 如果在第一列，直接赋值0
      if (j === 0) { 
        T[i][j] = 0;
        continue;
      }
      // 如果在第一行，直接判断能不能放进第0个物品
      if(i == 0){
        if(j >= weights[i]){
          T[i][j] = values[i]
        }else{
          T[i][j] = 0
        }
        continue;
      }
      // 不在第一行和第一列
      if (j < weights[i]) { // 如果容量小于当前行物品,参照上一行
        T[i][j] = T[i - 1][j];
      }else { // 如果容量大于等于当前行物品,取(上一行该容量的价值)和(放入该物品的价值+剩余空间的最大价值)的较大值
        T[i][j] = Math.max(T[i - 1][j], values[i]+T[i - 1][j - weights[i]])
      }
    }

  }
  find(weights,values,capacity,T)
  console.log('构建出的二维数组T为：',T)
  return T[n-1][capacity]
}

// 找到所选物品
function find(weights,values,capacity,T){
  let i = weights.length-1,j = capacity
  while(i>0&&j>0){
    if(T[i][j] != T[i-1][j]){
      console.log(`选择了物品${i}重量为${weights[i]}价格为${values[i]}`)
      i--
      j = j-weights[i]
    }else{
      i--      
    }
    if(i == 0){
      if(T[i][j] != 0){
        console.log(`选择了物品${i}重量为${weights[i]}价格为${values[i]}`)
      }
    }
  }
}

// 物品重量数组
let weights = [2,3,4]
// 物品价值数组
let values = [3,4,5]
// 背包容量
let capacity = 5

console.log(knapsack(weights,values,capacity))